/*
 * Copyright 2010 - 2011, The PLDesktop Development Team
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 *
 */

#ifndef PLRADIXTREENODE_H
#define PLRADIXTREENODE_H

#include <kernel/PLObject.h>
#include <string.h>

namespace PLSDK {

    template<class E>
    class PLRadixTree;

    /**
     * The inner node from a radix tree.
     * This was only for internal use.
     */
    class PLRadixTreeNode : public PLObject {
        friend class PLRadixTree<void*>;
    public:
        /**
         * Node pointer structure.
         */
        struct NodePtr {
            /**
             * The noder pointers.
             */
            PLRadixTreeNode *p[16];
        };
        /**
         * Match types from the nodes.
         */
        enum MatchType {
            /**
             * Key matched node key exactly.
             */
            ExactMatch,
            /**
             * Key didn't match node key at all.
             */
            NoMatch,
            /**
             * A subset of key matched the node key.
             */
            PartialMatch,
            /**
             * Key matched node key, and had extra characters.
             */
            OverMatch
        };
        /**
         * Constructor.
         */
        PLRadixTreeNode() : m_pKey(0),value(0),m_pParent(0),m_nChildren(0) {
            memset(reinterpret_cast<uint8_t*>(m_pChildren), 0, 16 * sizeof(NodePtr*));
        }
        /**
         * Destructor.
         */
        ~PLRadixTreeNode();
        /**
         * Get the next data structure in the list.
         *
         * @return pointer to the next data structure in the list.
         */
        inline PLRadixTreeNode *next() {
            return doNext();
        }
        /**
         * Get the previous data structure in the list.
         *
         * @return pointer to the previous data structure in the list.
         * @note Not implemented!
         */
        inline PLRadixTreeNode *previous() {
            return 0;
        }
        /**
         * Locates a child of this node, given the key portion of key
         * (lookahead on the first token).
         *
         * @param cpKey The key to search for.
         * @return pointer to the find child.
         */
        PLRadixTreeNode *findChild(const uint8_t *cpKey);
        /**
         * Adds a new child.
         *
         * @param pNode The node to add.
         */
        void addChild(PLRadixTreeNode *pNode);
        /**
         * Replace a node.
         *
         * @param pNodeOld The node to replace.
         * @param pNodeNew The node to set.
         */
        void replaceChild(PLRadixTreeNode *pNodeOld, PLRadixTreeNode *pNodeNew);
        /**
         * Remove a node.
         *
         * @param pChild The child to remove.
         */
        void removeChild(PLRadixTreeNode *pChild);
        /**
         * Compares cpKey and this node's key, returning the type of match
         * found.
         *
         * @param cpKey The key to search for.
         * @return The type for the found match.
         */
        MatchType matchKey(const uint8_t *cpKey);
        /**
         * Get the first child node.
         *
         * @return The node.
         */
        PLRadixTreeNode *getFirstChild();
        /**
         * Sets the node's key to the concatenation of \p cpKey and the
         * current key.
         *
         * @param cpKey Key to prepend to the current key.
         */
        void prependKey(const uint8_t *cpKey);
        /**
         * Set a key to the node.
         *
         * @param cpKey The key to set.
         */
        void setKey(const uint8_t *cpKey);
        /**
         * Get the key of the node.
         *
         * @return The key.
         */
        inline uint8_t *getKey() {
            return m_pKey;
        }
        /**
         * Set the value for the node.
         *
         * @param pV The value to set.
         */
        inline void setValue(void *pV) {
            value = pV;
        }
        /**
         * Get the value from the node.
         *
         * @return The value.
         */
        inline void *getValue() {
            return value;
        }
        /**
         * Set the parent node.
         *
         * @param pP The parent node.
         */
        inline void setParent(PLRadixTreeNode *pP) {
            m_pParent = pP;
        }
        /**
         * Get the parent node.
         *
         * @return The parent node.
         */
        inline PLRadixTreeNode *getParent() {
            return m_pParent;
        }
    private:
        // Node key, zero terminated.
        uint8_t *m_pKey;
        // Node value.
        // Parting from coding standard because Iterator requires the
        // member be called 'value'.
        void *value;
        // Array of 16 pointers to 16 nodes (256 total).
        NodePtr *m_pChildren[16];
        // Parent node.
        PLRadixTreeNode *m_pParent;
        // Number of children.
        size_t m_nChildren;
        PLRadixTreeNode(const PLRadixTreeNode&);
        PLRadixTreeNode &operator =(const PLRadixTreeNode&);
        // Returns the next Node to look at during an in-order iteration.
        PLRadixTreeNode *doNext();
        // Returns the node's next sibling, by looking at its parent's children.
        PLRadixTreeNode *getNextSibling();
    };

}

#endif
